Recursion and Self-Similarity: Koch Curves¶
Turtles all the way down¶
Let’s switch gears now and use recursion to draw some pretty pictures, specifically fractals. Fractals and recursion go together like chocolate and peanut butter, and seeing a figurative representation of recursion drawn line-by-line will further our understanding of how it works. We’ll start with the Koch curve.
In order draw the Koch curve, we’ll use Python’s turtle library. So before we can define any function, we have to import the library into our program, and create a turtle object that will draw lines for us. We’ll also specify a window, line width, background color, etc:
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.bgcolor('black')
t.color('orange')
t.pensize(5)
# we'll put our ``koch()`` function here
wn.exitonclick()
When you run this, you should see a black window pop up, with an orange cursor (the turtle) pointing to the right. Clicking on the window after the program has finished calls wn.exitonclick(), which deletes the window and exits the program. (Any print statements we choose to include during the design process will show up in the window from which you launch the program.) The turtle library has lots of features and we’ll only touch on a few of them here, so check out the documentation to see what else you can do with this simple but rich library.
Let’s begin by drawing a straight line. To do that, we’ll lift up the pen and position it somewhat to the left of the center of the screen (by default the turtle is placed at x-y coordinates (0, 0)). Now that we’re at (-500, 0) we’ll the pen ‘down’ so we can begin drawing:
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.bgcolor('black')
t.color('orange')
t.pensize(5)
t.penup()
t.setpos(-500, 0)
t.pendown()
t.speed()
def koch(t):
t.forward(1000)
koch(t)
wn.exitonclick()
Ok, so this may not look like much. But you may be surprised to learn that you have already drawn a fractal - in this case, a Koch curve of order 0. So what do other orders of the curve look like, and what does recursion have to do with it?
If a Koch curve of order 0 is a straight line, we generate further orders by trisecting the line, and inserting into the middle portion two lines joined at an acute angle. The length of each of the new lines is 1/3 of the total length of order 0. Traditionally, the inserted lines imply an equilateral triangle, but it can be any acute angle we like. This substitution increases the length of the curve by 33%. Crudely speaking, order 0 to order 1 looks like:
order 0: ______________
/\
/ \
order 1: ____/ \____
In order to move from order 1 to order 2, we see that we now have not one line to trisect, but four. The process gets repeated until we have trisected all available lines to the desired order (or ‘depth’, which you’ll see is nicely aligned with the concept of ‘depth-first search’ that we first explored in Multiple Recursive Calls: Fibonacci Sequence, Part 1).
/\
/ \
order 1: ____/ \____
__/\__
\ /
order 2: __/\__/ \__/\__
You can view several orders of the Koch curve generated here. However, this animation is deceptive, since it is not the way that recursion generates our curve.
Now that we know what we are after, let’s first figure out how to draw an order 1 curve from scratch. Here we will simply tell our turtle how far to go, how many degrees to turn, etc:
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.bgcolor('black')
t.color('orange')
t.pensize(5)
t.penup()
t.setpos(-500, 0)
t.pendown()
t.speed()
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
t.forward(size // 3) # Go 1/3 of the way
t.left(60)
t.forward(size // 3)
t.right(120)
t.forward(size // 3)
t.left(60)
t.forward(size // 3)
size = 1000
order = 1
koch(t, order, size)
wn.exitonclick()
In addition to the instructions to draw forwards, and turn left or right, I’ve made the program a bit more flexible by creating size and order variables and passing them as arguments to koch(). Since order 0 is the simplest possible statement of the problem, that seems like a good candidate for our base case. Otherwise, turtle trisects the given size and inserts the implied equilateral triangle in the center section.
Take a moment to understand that each next instruction to our turtle is executed from the turtle’s last position and direction. Also, by symmetry, if we turn 60° to the left and 120° to the right, it’s the same as turning 60° to the left and -120° to the left. Thus we can restate the drawing as a series of left-handed turns, a regularity that suggests that we can write the entire else block as a for loop:
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
t.forward(size // 3)
t.left(angle)
Question: Why do we need the final 0 in the list? What happens if we omit it?
Now that we have sorted out the 0th and 1st order curves, we can consider more complex forms. In fact, we’re ready to insert our recursive call. If you think about it, the above code essentially represents the base case and a single recursive case, except there’s no recursive call, which is how we connect the recursive case to the base case.
Given the way we have written our function, we know we need to pass t, order and size as the arguments of our recursive call. If our base case is order == 0 then we ought to be decrementing our way towards the base case by order - 1. So a good working hypothesis for our recursive call is koch(t, order - 1, size). Of course, it has to be inside koch(), but where to put it?
First think about where the recursive call wouldn’t go. Obviously, we don’t need it in the base case, so it must be somewhere in the else block. All the action is happening inside the for loop, so probably somewhere inside there. Now consider the two statements in the loop: one makes the turtle draw a line, the other turns the turtle by a certain angle. We are certainly not interested in modifying the angles, so the only piece of code that makes sense to address is t.forward(size // 3).
Are we inserting the recursive call before or after drawing the line, or is something else involved? If you consult the animation above, you’ll notice that there is a pattern of substitution occurring that depends on the order curve we want. Let’s look at how we get from an order 1 to an order 2 Koch curve:
/\
b/ \c
order 1: _____/ \_____
a d
b__/\__c
\ /
order 2: __/\__/ \__/\__
a d
For every segment a, b, c, d we want to insert a trisection, which implies an additional iteration of koch(). So it looks like we want to actually replace ``t.forward(size // 3)`` with the recursive call. But if we get rid of ``t.forward(size // 3)`` what will do the actual drawing? This is where the base case comes in, as ``t.forward(size)`` is pretty much the only thing it does.
Putting it all together, our recursive function looks like this:
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(t, order - 1, size)
t.left(angle)
This looks good, right? Except if you run it, the turtle will quickly run off the screen and you won’t see more than a couple of segments of the curve. I failed to modify the recursive function’s size argument, so in the process of recursing we also super-sized the drawing. We really want to keep fixed the distance between the start and the end of our drawing. No matter how many orders of recursion we request, we have to begin at (-500, 0) and end at (500, 0). Since we are operating on a third of the length of size, we want that proportion to be preserved, hence we modify our recursive call to reflect this: koch(t, order - 1, size // 3).
With that modification, our final code looks like this:
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.bgcolor('black')
t.color('orange')
t.pensize(5)
t.penup()
t.setpos(-500, 0)
t.pendown()
t.speed(0) #fastest draw setting, 10 is slowest
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(t, order - 1, size // 3)
t.left(angle)
size = 1000
order = 3
koch(t, order, size)
wn.exitonclick()
If we draw the Koch curve using a higher order, say 3 or 4, the final curve is drawn perfectly, starting from the first segment and all the way to the last. This is very different from the YouTube animation above, which showed a complete rendering of one order before moving on to the next. It tells us something important about the way recursion is functioning both here, and generally.
Tracing the recursive calls¶
As we’ve discussed before, every time a recursive call is invoked, the current function is interrupted and the program flow pursues the recursion until it reaches the base case (or is otherwise interrupted, as we saw with pal()). So koch() is going to keep recursing until it reaches the base case, and only then will it begin drawing. In terms of frames, our ‘talking algorithm’ would narrate the recursion for order 3 as follows:
- Global frame says, “Please compute
koch(t, 3, 1000)” - Frame 1 says, “I can’t compute
koch(t, 3, 1000)because I first need to computekoch(t, 2, 333)” - Frame 2 says, “I can’t compute
koch(t, 2, 333)because I first need to computekoch(t, 1, 111)” - Frame 3 says, “I can’t compute
koch(t, 1, 111)because I first need to computekoch(t, 0, 37)” - Frame 4 says, “I found the base case: I know how to compute
koch(t, 0, 37)! Here you go:”
_______________
Wait, what? Where’s the rest of it? Let’s go back to the code and unpack it by expanding the for loop into a series of statements similar to what we had earlier, but where t.forward(size // 3) is replaced by the recursive call:
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
koch(t, order - 1, size // 3)
t.left(60)
koch(t, order - 1, size // 3)
t.right(120)
koch(t, order - 1, size // 3)
t.left(60)
koch(t, order - 1, size // 3)
Ah. It’s now clear that the first recursive call only asked turtle to get to the base case and, once it got there, drew a line with length of 37. After that, we moved on to t.left(60), where we repositioned the turtle at an angle of 60° to the left. We recursed once again until we drew, using the base case, another segment of length 37. Following a rightward turn of 120° (or leftward turn of -120°, as we wrote in the for loop), we drew the third segment. The final recursive call is executed after another leftward 60° turn, leaving us with…
/\
/ \
_____/ \_____
…but always drawn in terms of the subdivision of length that corresponds with how many calls it took us to get to the base case - in this case, a segment length of 37. So we know that the only time the program draws anything will be at the base case, and it will be that smallest length, which corresponds to the number of divisions by 3 needed to reach order 0. That is, if we only drew an order 1 curve (ie, one trisection), at size == 1000 and order == 1, we would have size // 3 == 333 at order == 0, so every length drawn would have to be 333.
Here is a diagram that shows the tree created by this series of recursive calls:
Figure 1. Order 1 call tree for koch()
If this is a complete iteration of the else block, the next reasonable question is: How do we begin the next trisection at the correct angle? Or, how do we go from…
__/
\
__/\__ …to… __/\__/ …?
After all, if we only run the program using order == 1 it finishes with the turtle pointing straight to the left and not angled upwards by 60°. Let’s look at a diagram for order == 2 to better understand what’s going on:
Figure 2. Order 2 call tree for koch()
The turn happens when frame 2 has run through all of its statements and is discarded. Where does this put us? Back at frame 1, at the next statement: t.left(60)! Once the program turns left by 60°, the next recursive call goes into effect. Frame 3 will go through the same set of drawings and turns for the second call, then turn right 120°, repeat, and finally do the same for one more repetition after turning left 60°. While Figure 2 only shows half of order == 2, if we continue assigning each subset of four lines a letter, we can see the following, where A, C, E and G are completed recursive calls, and B, D and F are turtle turns:
D
C__/\__E
\ /
__/\__/ \__/\__
A B F G
…
else:
koch(t, order - 1, size//3) # A
t.left(60) # B
koch(t, order - 1, size//3) # C
t.right(120) # D
koch(t, order - 1, size//3) # E
t.left(60) # F
koch(t, order - 1, size//3) # G
We’ve already seen the consequences of multiple recursive calls with the Fibonacci sequence. In that case, two recursive calls created two branches per node (or frame). In the accompanying exercise, the tribonacci sequence called for three recursive calls per function. With koch() we have no less than four.
Just as with fib() and trib(), once a function is called, the recursion must continue until it’s complete. This rule still holds even when we are confronted with multiple recursive calls in a single function. In fact it makes it easier to think through the function, since you only need to be concerned with working your way through one thread at a time. We thought of fib() as recursing all the way down the ‘left-hand’ side of the call tree. In the same way, the first koch(t, order-1, size // 3) call resolves every subsequent first koch(t, order-1, size // 3) call. But when we get to a base case, we know that the next three recursive calls will also hit the base case right away. This is what allows the drawing to keep its integrity.
Another essential detail about koch() is the lack of return statements, or any variables that capture the output of the recursed call. It’s simply not necessary. The program is basically saying, ‘at this point just get to the base case, do what it says and then carry on with the next line’. There’s nothing to return, nothing to store, and (unlike fib() and trib()) no additional computation needed beyond the execution of the base case itself. All it does is draw the line of the correct length. The subsequent line of code positions the turtle at the correct angle to draw the next line - but only once the preceding recursive call has returned from the base case.
The Koch snowflake¶
We can now extend the Koch curve into what is known as the Koch snowflake. Instead of executing orders of recursion on a single line, let’s do the same trisection on each side of a triangle. A good way to begin thinking about this is to ask: What is an order 0 snowflake? If an order 0 curve is a straight line, it stands to reason that an order 0 snowflake is simply a triangle.
So we first make sure we can draw a triangle. We’ll reposition our starting point and shorten the initial length so that everything fits on the screen (well, it fits on my screen - you may have to fiddle with the values to ensure it fits yours). Then we’ll declare a separate function that will draw an equilateral triangle in a way very similar to what we’ve done above:
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.bgcolor('black')
t.color("orange")
t.pensize(5)
t.penup()
t.setpos(-450, 250)
t.pendown()
t.speed(0)
def triangle(size):
for angle in [-120, -120, 0]:
t.forward(size)
t.left(angle)
size = 900
triangle(size)
Now let’s think how we can apply koch() to a polygon as opposed to simply a line. Well, a polygon is just lines joined at angles, so we want to build the curve on a per-line basis. That is, we don’t need to consider the polygon as a whole. As long as we have the instructions to, on the one hand, build the polygon, and on the other, build a curve for each line, we should be in good shape, so to speak.
Thinking this way is helpful because otherwise you may find yourself considering how to integrate the polygon with koch() in a way that is overly complicated. The description I’ve just offered implies a division of labor:
- Set up the polygon.
- In place of drawing the first line of the polygon, call
koch()and let it do the work. - When the first side is completed, turn the turtle at the appropriate angle.
- Invoke
koch()again. - Continue until all sides have been completed and the turtle is back where it started.
The other implication is that we would be better off computing our polygon and our curve separately. There’s no beter way to do that than to write separate functions. Assuming we change nothing about koch(), what does this mean for triangle()? Here’s a first draft, so we can just see the two functions together:
def triangle(size):
for angle in [-120, -120, 0]:
t.forward(size)
t.left(angle)
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
koch(t, order - 1, size // 3)
t.left(60)
koch(t, order - 1, size // 3)
t.right(120)
koch(t, order - 1, size // 3)
t.left(60)
koch(t, order - 1, size // 3)
Now, how do we get the two functions talking to one another? Let’s go back to how we set up our recursive call in koch(). We quickly established that we wanted to substitute t.forward(size // 3) with the recursive call koch(t, order - 1, size // 3). Consulting our pseudocode above, you can see a similar opportunity: in triangle(), `t.forward(size) is exactly where we want koch() to do its work. Here is our final code, with the re-introduction of the for loop in koch():
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.bgcolor('black')
t.color("orange")
t.pensize(5)
t.penup()
t.setpos(-450, 250)
t.pendown()
t.speed(0)
def triangle(size):
for angle in [-120, -120, 0]:
koch(t, order, size)
t.left(angle)
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(t, order - 1, size // 3)
t.left(angle)
size = 900
order = 3
triangle(size)
wn.exitonclick()
Heuristics and Exercises¶
♦ The simplest form of a fractal is known as order 0. When creating a recursively drawn solution, first learn how to draw that shape, and then use that as the base case. Then design the code that would draw the order 1 shape, using a simple if/else branching. Your next step should be to design the recursive call that links the two, such that all recursive calls ultimately resolve themselves at the base case.
♦ In some cases, for exampe when the purpose of the program is drawing, you may not even need to return a value from a recursive call, or store it in a variable. It’s completely sufficient to get to the base case, and simply allow the code to continue executing.
Exercise: An n-flake is any polygon whose lines are recursively replaced with the polygon itself. Obviously, the Koch snowflake is one such n-flake. Modify koch() to an n-flake whose order 0 is a square, and which ‘grows’ squares on the same trisected basis as the Koch curve. At what depth do the new squares begin to overlap? At what depth do the drawing’s details become almost imperceptible? Can you think of a way to ‘magnify’ the view of a part of the pattern?
You may want to use the methods t.fillcolor(), t.begin_fill() and t.end_fill() to fill in the polygon, and play around with other parameters, such as pensize(), to get a better view of what’s going on.
Credit: Much of this material adapted from Chapter 18.1 of the fantastic resource, Think Like A Computer Scientist